Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Nested List Weight Sum

Problem Statement

You are given a nestedList. Each element of the nestedList contains either integers or other such nested lists.

The depth level is determined by how many levels of nested lists the integer is within. For example, each element of the list [1, 1, [2], [2, [3]]] represents the depth of itself.

Return the sum of all integers of the list after multiplying each integer with its depth level.

Examples

  • Example 1:

    • Input: [[2, [3, 4]], [5, 6], 7]
    • Expected Output: 54
    • Justification: The sum is calculated as 4 (2 at depth 2) + 9 (3 at depth 3) + 12 (4 at depth 3) + 10 (5 at depth 2) + 12 (6 at depth 2) + 7 (7 at depth 1).
  • Example 2:

    • Input: [1, [4, [6]]]
    • Expected Output: 27
    • Justification: The sum is 1 (depth 1) + 8 (4 at depth 2) + 18 (6 at depth 3).
  • Example 3:

    • Input: [5, [2, [3, [4]]], 1]
    • Expected Output: 35
    • Justification: The calculation is 5 (depth 1) + 4 (2 at depth 2) + 9 (3 at depth 3) + 16 (4 at depth 4) + 1 (depth 1).

Solution

To solve this problem, a recursive approach is ideal. This approach works by traversing each element in the list. If the element is an integer, we multiply it by its depth and add it to the total sum. If the element is another list, we recursively process this list, increasing the depth by one.

This method is effective because it naturally handles the nested structure of the input and ensures that each integer is multiplied by its correct depth level. The recursion elegantly simplifies the process of diving into nested lists and accumulating the weighted sum.

Step-by-Step Algorithm

  • Define a method nestedSum which takes a nested list and an integer depth.
  • Initialize a variable totalSum to 0.
  • Iterate through each element in the nested list.
    • If the element is an integer, add it to totalSum multiplied by depth.
    • If the element is a list, recursively call nestedSum with the list and depth + 1, and add the result to totalSum.
  • Return totalSum.

Algorithm Walkthrough

Let's consider the input: [[2, [3, 4]], [5, 6], 7].

  1. Start with the outer list: [[2, [3, 4]], [5, 6], 7] with depth = 1.
  2. The first element is [2, [3, 4]]. It's a nested list, so we process its elements:
    • 2 is an integer at depth = 2. Add 2 * 2 = 4 to totalSum.
    • [3, 4] is another nested list. Process its elements at depth = 3:
      • 3 is an integer. Add 3 * 3 = 9 to totalSum.
      • 4 is an integer. Add 4 * 3 = 12 to totalSum.
  3. The second element is [5, 6], another list at depth = 2. Process its elements:
    • 5 is an integer. Add 5 * 2 = 10 to totalSum.
    • 6 is an integer. Add 6 * 2 = 12 to totalSum.
  4. The third element is 7, a single integer at depth = 1. Add 7 * 1 = 7 to totalSum.
  5. Summing all these, the total sum is 4 + 9 + 12 + 10 + 12 + 7 = 54.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: O(N), where N is the total number of elements in the list, including nested lists. This is because each element is processed exactly once.
  • Space Complexity: O(D), where D is the maximum depth of the nested lists. This is due to the recursive stack.
Nested List Weight Sum (medium)
Dot Product of Two Sparse Vectors (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis